package algorithm.tree;

import algorithm.model.TreeNode;

import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.Stream;

/**
 * leetcode: https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/
 * Difficulty : Medium
 *
 * Z字，层序 遍历二叉树，先左后右
 * 思路:
 * 正常的层序遍历，遇到偶数的层数 Collections.reverse() 即可
 * 使用 Queue 可以变得更快,因为不用每层都创建一个对象了
 *
 * Created by yzy on 2021-02-03 14:33
 */
public class BinaryTreeZigZagOrderTraversal {

    /**
     * 7ms, beats 16.96%
     * 38.7MB, beats 14.93%
     *
     * @param root
     * @return
     */
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> resList = new ArrayList<>();
        if (root == null) return resList;

        List<TreeNode> currLevelNodeList = new ArrayList<>();
        currLevelNodeList.add(root);
        int level = 1;
        while (currLevelNodeList.size() > 0) {
            List<Integer> currLevelList = new ArrayList<>();
            resList.add(currLevelList);
            currLevelNodeList = currLevelNodeList.stream().flatMap(node -> {
                currLevelList.add(node.val);
                return Stream.of(node.left, node.right);
                    }).filter(node -> node != null).collect(Collectors.toList());
            if (level++ % 2 == 0) {
                Collections.reverse(currLevelList);
            }
        }
        return resList;
    }


    /**
     * 1ms,beats 98.62%
     * 38.8MB, beats 5.15%
     * @param root
     * @return
     */
    public List<List<Integer>> zigzagLevelOrder_Queue(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> resList = new ArrayList<>();
        if(root == null) {
            return resList;
        }

        queue.offer(root);
        int level = 1;

        while(queue.size() > 0){
            int size = queue.size();
            List<Integer> currList = new ArrayList<>();
            for(int i=0; i<size; i++){
                TreeNode node = queue.poll();
                currList.add(node.val);
                if(node.left != null) queue.offer(node.left);
                if(node.right != null) queue.offer(node.right);
            }
            if(level++% 2 == 0){
                Collections.reverse(currList);
            }
            resList.add(currList);
        }

        return resList;
    }
}
